package com.study.lu.动态规划;

public class 环形子数组的最大和 {
    /**
     * 给定一个长度为 n 的环形整数数组nums，返回nums的非空 子数组 的最大可能和。
     * <p>
     * 环形数组意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i]的前一个元素是 nums[(i - 1 + n) % n] 。
     * <p>
     * 子数组 最多只能包含固定缓冲区nums中的每个元素一次。形式上，对于子数组nums[i], nums[i + 1], ..., nums[j]，不存在i <= k1, k2 <= j其中k1 % n == k2 % n。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,-2,3,-2]
     * 输出：3
     * 解释：从子数组 [3] 得到最大和 3
     * 示例 2：
     * <p>
     * 输入：nums = [5,-3,5]
     * 输出：10
     * 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
     * 示例 3：
     * <p>
     * 输入：nums = [3,-2,2,-3]
     * 输出：3
     * 解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/maximum-sum-circular-subarray
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param args
     */
    public static void main(String[] args) {

        //int[] nums = new int[]{1,-2,3,-2};
        int[] nums = new int[]{-3,-2,-3};
        //int[] nums = new int[]{1,-6,-7,4};
        System.out.println(maxSubarraySumCircular(nums));

    }

    /**
     * 1.如果最大值不在环中，直接参考 最大子数组和.class ；
     * 2.如果最大值存在环中，则说明环中存在负数，那么只需要找到最小负数之和，数组之和减去最小负数之和即为最大值，
     * 3.比较2 1中的最大值
     * @param nums
     * @return
     */
    public static int maxSubarraySumCircular(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }

        int max=nums[0];
        int dpn_1=nums[0];
        int sum =nums[0];
        for(int i = 1;i<nums.length;i++){
            sum+=nums[i];
            int dpn= Math.max(nums[i],dpn_1+nums[i]);
            max = Math.max(dpn,max);
            dpn_1 = dpn;
        }

        int min = nums[0];
        int min_dpn_1=nums[0];
        for(int i = 1;i<nums.length;i++){
            int dpn= Math.min(nums[i],min_dpn_1+nums[i]);
            min = Math.min(dpn,min);
            min_dpn_1 = dpn;
        }

        return Math.max(sum-min,max);

    }
}
